package cn.zeronote.leetcode;

public class X53 {

    public int search(int[] nums, int target) {
        if (nums.length == 1 && nums[0] == target) {
            return 1;
        }

        int r = findRight(nums, target);
        if (r == -1) {
            return 0;
        }
        int l = findLeft(nums, target);
        return r - l + 1;
    }

    private int findLeft(int[] nums, int target) {
        int l = 0;
        int r = nums.length -1;
        int mid = -1;
        while(l < r) {
            mid = (r + l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }

            if (nums[l] == target) {
                return l;
            }
        }
        return -1;
    }

    private int findRight(int[] nums, int target) {
        int l = 0;
        int r = nums.length -1;
        int mid = -1;
        while(l < r) {
            mid = (r + l) / 2 + 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }

            if (nums[r] == target) {
                return r;
            }
        }
        return -1;
    }

}
